#! /usr/bin/env python
# -*- coding: utf-8 -*-
# vim:fenc=utf-8
#
# Copyright © 2018 crane <crane@crane-pc>
#
# Distributed under terms of the MIT license.


class TreeNode:
    def __init__(self, val):
        self.val = val
        self.left, self.right = None, None


class Solution:
    def maxDepth(self, root):
        # return self.rec_max_depth(root)
        return self.non_rec_max_depth(root)

    def non_rec_max_depth(self, root):
        INIT = 0
        LEFT_DONE = 1
        RIGHT_DONE = 2

        depth_stack = []
        node_stack = []

        node_stack.append([root, INIT])

        while node_stack:
            node, state = node_state = node_stack[-1]
            if node is None:
                # print('None')
                node_stack.pop()
                depth_stack.append(0)
                continue

            # print(node.val)
            if state == INIT:
                # print('init')
                node_state[1] = LEFT_DONE
                node_stack.append([node.left, 0])
            elif state == LEFT_DONE:
                # print('left')
                node_state[1] = RIGHT_DONE
                node_stack.append([node.right, 0])
            else:
                assert state == RIGHT_DONE
                # print('right')
                node_stack.pop()
                depth = max(depth_stack.pop(), depth_stack.pop())
                depth_stack.append(depth + 1)


        return depth_stack.pop()

    def rec_max_depth(self, node):
        if not node:
            return 0

        left_depth, right_depth = self.rec_max_depth(node.left), self.rec_max_depth(node.right)

        return max(left_depth, right_depth) + 1


def main():
    print("start main")

    s = Solution()

    root = TreeNode(1)
    root.left = TreeNode(2)
    ret = s.maxDepth(root)
    # ret = s.maxDepth(None)
    print(ret)

if __name__ == "__main__":
    main()
